Phát hiện chu trình

Trong Khoa học máy tính, bài toán phát hiện chu trình hay tìm chu trình là bài tìm thuật toán tìm vòng lặp trong một chuỗi giá trị hàm.Bất kỳ hàm f {\displaystyle f} nào ánh xạ một tập hữu hạn S {\displaystyle S} tới chính nó, và bất kỳ giá trị ban đầu x 0 {\displaystyle x_{0}} trong S {\displaystyle S} , chuỗi các giá trị hàmphải có một giá trị xuất hiện hai lần: có một số cặp i và j phân biệt sao cho x i = x j {\displaystyle x_{i}=x_{j}} . Khi điều này xảy ra, chuỗi tiếp tục chu trình một cách định kỳ, bằng cách lặp lại chuỗi giá trị từ x i {\displaystyle x_{i}} tới x j − 1 {\displaystyle x_{j-1}} . Tìm chu trình là bài toán tìm i và j khi biết f {\displaystyle f} và x 0 {\displaystyle x_{0}} .Rất nhiều thuật toán tìm chu trình nhanh và dùng ít bộ nhớ được biết. Thuật toán rùa và thỏ của Robert W.Floyd di chuyển hai con trỏ với vận tốc khác nhau qua chuỗi cho đến khi chúng cùng chỉ một giá trị. Lựa chọn khác, ta có thuật toán của Brent dựa trên ý tưởng tìm kiếm theo cấp số mũ. Cả hai thuật toán trên chỉ dùng một số lượng cố định bộ nhớ và tính giá trị hàm một lượng tỷ lệ thuận với khoảng cách tính từ xuất phát của chuỗi đến giá trị lặp đầu tiên. Các thuật toán khác đổi bộ nhớ lớn hơn để tính ít hơn số lần tính giá trị hàm.Ứng dụng của phát hiện chu trình bao gồm thử nghiệm chất lượng của bộ sinh số giả ngẫu nhiênhàm băm mật mã học, các thuật toán trong lý thuyết số tính toán, phát hiện vòng lặp vô hạn trong các chương trình máy tính và các cấu hình tuần hoàn trong tế bào tự động hóa.